package mht.practice.sort;

/**
 * Created by MHT on 2017/8/26.
 */
public class InsertionSort2 {

    //我们的算法类不允许产生任何实例
    private InsertionSort2(){}

    //数组中两个元素进行位置交换
    private static void swap(Object arr[],int i,int j){
        Object temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // 对arr[l...r]的区间使用InsertionSort排序 优化版本
    public static void sort(Comparable arr[],int l,int r){

        assert l >= 0 && l <= r && r < arr.length;

        for( int i = l + 1 ; i <= r ; i ++ ){
            Comparable e = arr[i];
            int j = i;
            for( ; j > l && arr[j-1].compareTo(e) > 0 ; j--)
                arr[j] = arr[j-1];
            arr[j] = e;
        }
    }

    // 对整个arr数组使用InsertionSort排序 优化版本
    public static void sort(Comparable arr[]){

        int n = arr.length;
        for (int i=0;i<n;i++){
            // 寻找元素arr[i]合适的插入位置
            Comparable e = arr[i];
            int j;
            for( j = i; j > 0 && arr[j-1].compareTo(e) > 0 ; j--){
                arr[j] = arr[j-1];
            }
            arr[j] = e;
        }
    }
}
